/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
var coinChange = function (coins, amount) {
  //创建一个长度为 amount+1 的数组 dp，初始值为 Infinity
  const dp = new Array(amount + 1).fill(Infinity)
  //dp[0]=0表示金额0时所需要的最小硬币数量为0
  dp[0] = 0

  // 遍历每个金额从 1 到 amount
  for (let i = 1; i <= amount; i++) {
    // 遍历每种硬币面值
    for (let coin of coins) {
      // 如果当前硬币面值小于等于当前金额 i
      if (coin <= i) {
        // 更新 dp[i] 的值，取当前值和 dp[i-coin]+1 中的较小值
        dp[i] = Math.min(dp[i], dp[i - coin] + 1)
      }
    }
  }

  //如果dp[amount]为Infinity，说明没有找到匹配的方案，返回-1
  return dp[amount] === Infinity ? -1 : dp[amount]

};